/**
 *https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/submissions/545773496/
 * 121.买股票的最佳时机
 * easy 2024.07.11
 * dp
 */

class Solution {
public:
    //    题解方法更好
    int maxProfit(vector<int>& prices) {          
        // vector<int> p=prices;
        int n=prices.size();
        if(n==1)
        return 0;
        vector<int> p=prices;
        prices[0]*=-1;
        int k=prices[0];
        for(int i=1;i<n;i++){
            if(prices[i-1]==-p[i-1]){
                k=prices[i-1];
                prices[i]=max(-prices[i],prices[i]+prices[i-1]);
            }else if(k<=0){
                prices[i]=max({prices[i-1],prices[i]+k,prices[i]-p[i-1]});
                if(-p[i]>k)
                k=-p[i];
            }
            else if(prices[i-1]<0)
                prices[i]=max({-prices[i],prices[i-1],prices[i]-p[i-1]});
            else
                 prices[i]=max({-prices[i],prices[i]-prices[i-1],prices[i-1]});
        }
        if(prices[n-1]<0)
        return 0;
        return prices[n-1];
    }
};